Реферат

У даній роботі викладені основні принципи розв'язання транспортної задачі, зокрема ¾ задача про комівояжера.
У роботі використано 5 джерел, вона містить 29 сторінок, 2 додатки, програму, написану на мові Сі.

Зміст

"1-3" \ n \ p ""

Реферат
Зміст
Введення
1.Постановка задачі про комівояжера
2. Метод гілок і меж
3. Використання верхніх оцінок
4. Рішення із заданою точністю
Висновок
Список використаної літератури
Додаток 1
Додаток 2

Введення

Проблема оптимізації є в певному сенсі, мабуть, найгострішою проблемою сучасності. У будь-якій сфері діяльності людина завжди шукає оптимальне рішення.
Існує клас задач, які не задовольняють принципом оптимальності, і, отже, для цих завдань метод динамічного програмування безпосередньо використаний бути не може. Їх вирішення вимагає розвитку спеціальних способів послідовного аналізу варіантів. Зокрема, до такого класу завдань відноситься задача про комівояжера (бродячому торговця).
Дана робота описує знаходження оптимального рішення задачі про комівояжера, застосовуючи метод гілок і меж.

1.Постановка задачі про комівояжера
Розглянемо задачу про комівояжера (бродячому торговця). Припустимо, що бродячий торговець повинен, покинувши місто, якому ми призначимо номер 1 (рис. 1), об'їхати ще N-1 міст і повернутися знову в місто номер 1. У його розпорядженні є дороги, що з'єднують ці міста. Він повинен вибрати свій маршрут - порядок відвідування міст так, щоб шлях, який йому доведеться пройти, був якомога коротшим. Основна умова цієї задачі полягає в тому, що комівояжер не має права повертатися знову до того міста, в якому він одного разу вже побував. Ця умова будемо називати умовою (a). Ми вважаємо, що відстань між двома містами - функція - Визначено. Зрозуміло, функція може означати не тільки відстань, але, наприклад, час або витрати в дорозі і т. д. Тому в загальному випадку , А функції природно приписати значення ¥. Довжина l шляху S визначається формулою:
. (1)
Сума у ​​виразі (1) поширена по всіх індексах i і j, що задовольняє умові (a), тобто умові, що кожен з індексів i і j входить у вираз (1) один і тільки один раз. Функція є, таким чином, адитивної - вона подана в вигляді суми доданків, проте саме завдання - завдання відшукання мінімуму l - в силу обмеження (a) не є адитивною і не задовольняє принципу оптимальності.

8

4

2

7

5

6

3

1

Рис.1.
Розглянемо площину t, х, де t - дискретний аргумент, що приймає значення
0, 1, 2,. . . , N, відповідні етапам подорожі бродячого торговця. Значення t = 0 відповідає його початкового стану в місті номер 1, t - 1 - переходу з міста номер 1 в місто, яке він вибрав першим для відвідування, і т. д., t = N означає останній етап його подорожі - повернення в місто номер 1. Аргумент х тепер також приймає дискретні значення 1, 2,. . . , N (рис. 2). З'єднаємо точку (0,1) з точками (1,1), (1,2), ..., (, 1N) і довжинам відрізків, що з'єднують ці точки, припишемо значення . Далі точки (1, s) - вузли, що лежать на першій вертикалі, ми з'єднаємо з усіма вузлами другого вертикалі, довжинам відрізків ми припишемо значення і т. д. Точки (N-1, s) з'єднаємо з точкою (N, 1). У результаті ми побудували деякий граф, кожна ламана якого, з'єднує точку (0,1) з крапкою (N, 1), описує шлях комівояжера. Нашу завдання ми можемо тепер сформулювати наступним чином. Серед всіх ламаних, що належать цьому графу і з'єднують точки (0,1) і (N, 1), і задовольняють умові (a), знайти ламану найкоротшою довжини. Умова (a) полягає тепер в тому, що шукана ламана перетинає (у вузлі) кожної з прямих x = i один і тільки один раз.

Рис. 2.
Розглянемо вузол Р, що лежить на третій вертикалі (див. рис. 2). Якщо б умову (a) було відсутнє, то вибір траєкторії, яка з'єднує точку Р з точкою (N, 1), не залежав би від того шляху, який привів нас в точку Р. У даному випадку ситуація інша, і якщо два комівояжера знаходяться в точці Р, але один із них прийшов в цей стан, рухаючись вздовж траєкторії, що проходить через точку Q, а другий через точку R, то їх стану істотно відрізняються один від одного. Комівояжер, який рухався по другій траєкторії, вже побував у містах номер 2 та номер 5 і в майбутньому він вже не має права знову заїжджати, в ці міста. Що стосується комівояжера, який рухався вздовж першої траєкторії, то він побував у містах номер 3 і номер 6; він не має права повертатися в ці міста, але зате він ще зобов'язаний відвідати міста номер 2 і номер 5 і т.д.
Оскільки функція визначена на кінцевій множині точок, то і функція також визначена на кінцевій множині точок. Отже, завдання визначення мінімуму функції l зводиться до перебору деякого кінцевого безлічі значень цієї функції, і проблема носить суто обчислювальний характер. Однак саме обчислювальні труднощі тут величезні. Легко підрахувати, що кількість можливих варіантів (число значень функції l) дорівнює (N-1)!. Таким чином, безпосередньо перебрати і порівняти між собою всі можливі шляхи, по яким може слідувати бродячий торговець, для чималої кількості міст практично неможливо. Виникає проблема побудови такого методу послідовного аналізу варіантів, який виділяв би по можливості велику кількість неперспективних варіантів і зводив завдання до перебору відносно невеликої кількості "підозрілих" варіантів.

2. Метод гілок і меж

Основа цього, нині широко розповсюдженого методу полягає в побудові нижніх оцінок рішення, які потім використовуються для відбракування неконкурентоспроможних варіантів.
Функція приймає кінцеве число значень , Які ми можемо представити у вигляді таблиці (рис. 3). Припустимо, що ми вибрали певний шлях S . Його довжина буде дорівнює
(2)
причому сума (2) поширена по i, j так, що кожен з індексів зустрічається в ній один і тільки один раз. Величини з двома однаковими індексами ми прийняли рівними ¥.
Так що в кожен з варіантів s входить тільки один елемент з кожного рядка і стовпця, то ми можемо виконати наступну операцію, яка тут називається приведенням матриці. Позначимо через h , Найменший елемент з рядка номери i і побудуємо нову матрицю C елементами
.
Матриця C визначає нове завдання комівояжера, яка, проте, як оптимальної буде мати ту ж послідовність міст. Між величинами і буде існувати, очевидно, наступна зв'язок:

Зауважимо, що в кожній з рядків матриці C буде тепер, принаймні, один нульовий елемент. Далі позначимо через найменший елемент матриці C , Що лежить в стовпці номера j, і побудуємо нову матрицю З з елементами

Величини h і називаються константами приведення. Оптимальна послідовність міст для задачі комівояжера з матрицею З буде, очевидно, такий же, як і для вихідної задачі, а довжини шляху для варіанта номера s в обох задачах будуть пов'язані між собою рівністю
, (3)
Де
, (4)
тобто дорівнює сумі констант приведення.
Позначимо через l * рішення задачі комівояжера, тобто
,
де мінімум береться по всіх варіантах s, задовольняє умові (a). Тоді величина буде найпростішої нижній оцінкою рішення:
(5)
Будемо розглядати тепер завдання комівояжера з матрицею З , Яку ми будемо називати наведеної матрицею.
Розглянемо шлях, що містить безпосередній перехід з міста номери i в місто номера j, тоді на шляху s, що містить цей перехід, ми будемо мати, очевидно, наступну нижню оцінку:

Отже, для тих переходів, для яких , Ми будемо мати знову оцінку (5). Природно очікувати, що найкоротший шлях містить один із таких переходів - приймемо це міркування в якості робочої гіпотези. Розглянемо один з переходів, для якого , І позначимо через множина всіх тих шляхів, які не містять переходу з i в j. Так як з міста i ми повинні кудись вийти, то безліч містить один з переходів i ® k, де k ¹ i; так як в місто номера j ми повинні прийти, то безліч містить перехід т ® i, де т ¹ i. Отже, певний шлях , З безлічі , Що містить переходи i ® k і т ® i, буде мати наступну нижню оцінку:
.
Позначимо через

Тоді очевидно, що для будь-якого безлічі шляхів ми будемо мати оцінку
(6)
Ми припускаємо виключити деякий безліч варіантів , Тому ми зацікавлені вибрати такий перехід i ® j, для якого оцінка (6) була б найвищою. Іншими словами, серед нульових елементів матриці С виберемо той, для якого максимально. Це число позначимо через . Таким чином, всі безліч можливих варіантів ми розбили на дві множини I і I . Для шляхів з безлічі I , Ми маємо сценку (5). Для шляхів з безлічі I оцінка буде такою:
. (7)
Розглянемо тепер безліч I , І матрицю З . Так як всі шляхи, що належать цій безлічі, містять перехід i ® j, то для його дослідження нам досить розглянути завдання комівояжера, в якій міста номерів i і j збігаються. Розмірність цього завдання буде вже дорівнює N - 1, а її матриця вийде з матриці С викреслюванням стовпця номера j і рядки номери i.
Оскільки перехід i ® j неможливий, то елемент приймаємо рівним нескінченності.
Розглянемо випадок N = 3 (рис. 4, а) і припустимо, що ми розглядаємо той варіант, який містить перехід 3 ® 2. Тоді задача комівояжера після викреслювання третього рядка та другого стовпця вироджується в тривіальну. Її матриця зображена на рис. 4, б). У цьому випадку ми маємо єдиний шлях, і його довжина буде, очевидно, дорівнює сумі

1 3 1 ¥ C1 2 C2 ¥ Рис. 4б.

1 2 3 1 ¥ С1 С1 2 С2 ¥ С2 3 С3 С3 ¥ Рис. 4а.

Отже, якщо в результаті викреслювання рядка номери i та стовпця номера j ми отримаємо матрицю другого порядку, то завдання можна вважати вирішеною.
Нехай тепер N> 3. Після викреслювання ми отримаємо матрицю порядку N-1> 2. З цією матрицею (N-1)-го порядку зробимо процедуру приведення. Матрицю, яку таким чином отримаємо, позначимо через , А через - Суму її констант приведення. Тоді для , Ми будемо мати оцінку
. (8)
На цьому перший крок алгоритму закінчений. У результаті одного кроку ми розбили безліч всіх можливих варіантів на дві множини , І для колій, які належать цим безліччю, ми отримали оцінки (8) і (7) (рис. 5).

_ EMBED Equation.3 ___ _ EMBED Equation.3 ___ _ EMBED Equation.3 ___ _ EMBED Equation.3 ___ _ EMBED Equation.3 ___ _ EMBED Equation.3 ___ _ EMBED Equation.3